//一、快速排序
function quickSort (arr) {
  // 1、找基准数，比他小的放左边，比他大的放右边，左右分别用两个数组存
  var base_num = arr[0];
  var left_arr = [];
  var right_arr = [];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < base_num) {
      left_arr.push(arr[i]);
    } else {
      right_arr.push(arr[i]);
    }
  }
  // 2、用回调对左右数组分别用快排，返回排序好的数组（数组是无序的才用快排，成员数量>=2）
  if (left_arr.length >= 2) left_arr = quickSort(left_arr);
  if (right_arr.length >= 2) right_arr = quickSort(right_arr);

  // 3、合并排序好之后的左数组、基准数、和右数组，并返回
  return left_arr.concat(base_num, right_arr);
}


// 二、跳台阶（记忆化递归）
// 条件：一只青蛙一次可以跳上1级或2级台阶
// 求：该青蛙跳上n级台阶有多少种跳法（先后次序不同也算不同的跳法）
// 递归表达式: f(n)=f(n-1)+f(n-2) 跳到第n级台阶的最后一步有两种
// 递归终止条件：n=1时有一种跳法，n=2时有两种跳法
function jumpFloor (n) {
  if (n <= 0) {
    return;
  } else if (n == 1) {
    return 1;
  } else if (n == 2) {
    return 2;
  }

  return jumpFloor(n - 1) + jumpFloor(n - 2);
}
// 记忆化递归
var jumpFloor = (function () {
  var cache = [, 1, 2];
  return function (n) {
    if (n <= 0) {
      return;
    } else if (cache[n] !== undefined) {
      return cache[n];
    };
    return cache[n] = jumpFloor(n - 1) + jumpFloor(n - 2);
  }
}());